package com.linyaonan.leetcode.easy._1122;

import java.util.*;

/**
 *
 * 给你两个数组，arr1 和 arr2，
 *
 * arr2 中的元素各不相同
 * arr2 中的每个元素都出现在 arr1 中
 * 对 arr1 中的元素进行排序，使 arr1 中项的相对顺序和 arr2 中的相对顺序相同。未在 arr2 中出现过的元素需要按照升序放在 arr1 的末尾。
 *
 *  
 *
 * 示例：
 *
 * 输入：arr1 = [2,3,1,3,2,4,6,7,9,2,19], arr2 = [2,1,4,3,9,6]
 * 输出：[2,2,2,1,4,3,3,9,6,7,19]
 *  
 *
 * 提示：
 *
 * arr1.length, arr2.length <= 1000
 * 0 <= arr1[i], arr2[i] <= 1000
 * arr2 中的元素 arr2[i] 各不相同
 * arr2 中的每个元素 arr2[i] 都出现在 arr1 中
 *
 *
 * @author: Lin
 * @date: 2020/1/7
 */
public class RelativeSortArray {
    public int[] relativeSortArray(int[] arr1, int[] arr2) {
        if (arr1.length == 0) {
            return arr1;
        }
        if (arr2.length == 0) {
            Arrays.sort(arr1);
            return arr1;
        }
        HashMap<Integer, Integer> map = new HashMap<>();
        for (int i : arr2) {
            map.put(i, 0);
        }
        List<Integer> last = new ArrayList<>();
        for (int t : arr1) {
            if (map.containsKey(t)) {
                map.put(t, map.get(t) + 1);
            } else {
                last.add(t);
            }
        }
        List<Integer> start = new ArrayList<>();
        for (int i : arr2) {
            Integer count = map.get(i);
            for (Integer u = 0; u < count; u++) {
                start.add(i);
            }
        }
        Collections.sort(last);
        start.addAll(last);
        int[] result = new int[start.size()];
        for (int i = 0; i < result.length; i++) {
            result[i] = start.get(i);
        }
        return result;
    }
}
